package com.leetcode.two_pointers;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/30 21:12
 */
public class ThreeSum_15 {

    public List<List<Integer>> threeSum(int[] nums) {
        // 先对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // 用三个游标来找到值
        // 固定左端指针，游标指针为中间两个指针
        for (int k = 0; k < nums.length - 2; k++) {
            // 右边都是大于0的数，可以退出
            if (nums[k] > 0) break;
            // 会出现重复解，跳过重复的数
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    // 跳过重复的i
                    while (i < j && nums[i] == nums[++i]) ;
                } else if (sum > 0) {
                    // 跳过重复的j值
                    while (i < j && nums[j] == nums[--j]) ;
                } else {
                    // 按序号添加当前的三个值
                    res.add(Arrays.asList(nums[k], nums[i], nums[j]));
                    while (i < j && nums[i] == nums[++i]) ;
                    while (i < j && nums[j] == nums[--j]) ;
                }
            }
        }
        return res;
    }

    static class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            for (int k = 0; k < nums.length - 2; k++) {
                // 当右边都为正数，必然不会有和为0的情况，直接退出
                if (nums[k] > 0) break;
                // 跳过所有重复的解，使用的k是重复数中的第一个，所以指针要跳到和k-1不相等的位置
                if (k > 0 && nums[k] == nums[k - 1]) continue;
                int i = k + 1, j = nums.length - 1;
                while (i < j) {
                    int sum = nums[k] + nums[i] + nums[j];
                    int left = nums[i], right = nums[j];
                    if (sum > 0) {
                        // 跳过所有重复的解
                        while (i < j && nums[j - 1] == right) j--;
                    } else if (sum < 0) {
                        // 跳过所有重复的解
                        while (i < j && nums[i + 1] == left) i++;
                    } else {
                        res.add(Arrays.asList(nums[k], nums[i], nums[j]));
                        while (i < j && nums[i + 1] == left) i++;
                        while (i < j && nums[j - 1] == right) j--;
                    }
                }
            }
            return res;
        }
    }

}
